/***********************************************************************
 *  Project：LinkList
 *  Function: 链表抽象数据类型的定义和实现
 *  Description: 每个节点都有后继节点,链表的优点是存储空间利用高效
 *  PROJECT_FILENAME: dataStruct.cbp 选择此文件打开已创建项目
 *  Author: coder-itl
 ***********************************************************************
 *  Copyright 2021-10-04-22.58.55 by coder-itl
 ***********************************************************************/

#include "stdio.h"
#include "stdlib.h"

#include "LinkList.h"


/**
 * 初始化链表
 * @param linkList  要初始化的链表
 * @param dataArray
 * @param length    链表长度
 */
void InitLinkList(LinkList *linkList, ElementType *dataArray, int length) {
    for (int i = 0; i < length; i++) {
        /**
         * InsertLinkList 调用插入方法
         * linkList 要插入的链表
         * position 插入的位置 => i+1
         */
        InsertLinkList(linkList, i + 1, dataArray[i]);
    }
}

/**
 * 在指定的位置插入元素 element
 * @param linkList  要执行插入的链表
 * @param position  要插入元素的位置
 * @param element   要插入的元素
 */
void InsertLinkList(LinkList *linkList, int position, ElementType element) {
    /* 1. 创建空节点并为数据域赋值 */
    /* 创建一个空节点,分配内存空间  */
    Node *node = (Node *) malloc(sizeof(Node));
    /* 设置元素数据 */
    node->data = element;
    /* 设置节点的后继节点为空 */
    node->next = NULL;
    /* 2. 找到要插入位置的节点 */
    if (position == 1) {
        /* 如果插入的是第一个元素,指向刚创建的节点 */
        linkList->next = node;
        /* 链表的长度自增 */
        linkList->length++;
        return;
    }
    /**
     * 通过循环找到要插入的节点的位置
     * currNode: 当前节点
     * */
    Node *currNode = linkList->next;
    for (int i = 1; currNode && i < position - 1; i++) {
        currNode = currNode->next;
    }
    /**
     * 3. 将节点插入并对接前面的节点
     *  如果当前节点不为空
     * */
    if (currNode) {
        node->next = currNode->next;
        currNode->next = node;
        linkList->length++;
    }
}

/**
 * 链表的输出
 * @param linkList
 */
void PrintLinkList(LinkList *linkList) {
    /* node: */
    Node *node = linkList->next;
    if (!node) {
        printf("链表为空!\n");
        /* 将链表置为空 */
        linkList->length = 0;
        return;
    }
    for (int i = 0; i < linkList->length; i++) {
        printf("%d\t%s", node->data.id, node->data.name);
        node = node->next;
        printf("\n");
    }
}

/**
 * 链表是否为空
 * @param linkList
 * @return TRUE / FALSE
 */
int IsLinkListEmpty(LinkList *linkList) {
    return linkList->length == 0 ? TRUE : FALSE;
}


/**
 * 返回指定位置的元素
 * @param linkList
 * @param position  指定位置
 * @return
 */
ElementType GetLinkListElement(LinkList *linkList, int position) {
    Node *node = linkList->next;
    for (int i = 1; node && i < position; i++) {
        node = node->next;
    }
    return node->data;
}


/**
 * 删除并返回指定位置的元素
 * @param linkList 要执行操作的链表
 * @param position  指定位置
 * @return 删除返回指定位置的元素
 */
ElementType DeleteLinkListElement(LinkList *linkList, int position){
    /* 被删除的元素 */
    ElementType element;
    /* 赋值一个不可能的值,用来判断是否删除成功 */
    element.id = -999;
    Node *node = NULL;
    /* 如果删除的是第一个 */
    if (position == 1) {
        node = linkList->next;
        if (node) {
            element = node->data;
            linkList->next = node->next;
            /* 释放被删除节点的内存 */
            free(node);
            /* 节点删除之后,链表的总长度减减 */
            linkList->length--;
        }
        return element;
    }
    /* 1. 找到要删除节点和它的前缀节点 */
    /* 2. 要删除节点->next 赋值给前缀节点->next */
    /* 3. 释放要删除的节点内存 */
    /* 前缀节点 */
    Node *preNode;
    node = linkList->next;
    for (int i = 1; node && i < position; i++) {
        preNode = node;
        node = node->next;
    }
    if (node) {
        element = node->data;
        preNode->next = node->next;
        free(node);
        linkList->length--;
    }
    return element;
}


/**
 * 清空链表
 * @param linkList
 */
void ClearLinkList(LinkList *linkList) {
    Node *node = linkList->next;
    Node *nextNode;
    while (node) {
        /* 先记录当前节点的下个节点,以便于释放当前节点的内存 */
        nextNode = node->next;
        free(node);
        node = nextNode;
    }
    linkList->next = NULL;
    linkList->length = 0;
}
